package problem16_16;

//面试题16.16.部分排序
//https://leetcode.cn/problems/sub-sort-lcci/description/

class Solution {
    public int[] subSort(int[] array) {
        int n = array.length;
        int l = 0, r = n-1;
        while(l+1 < n && array[l+1] >= array[l]) l++;
        while(r-1 >= 0 && array[r-1] <= array[r]) r--;
        if(l >= r) return new int[]{-1, -1};
        int max = array[l], min = array[l];
        for(int i = l; i<=r; i++) {
            max = Math.max(array[i], max);
            min = Math.min(array[i], min);
        }
        while(l-1 >= 0 && min < array[l-1]) l--;
        while(r+1 < n && max > array[r+1]) r++;
        return new int[]{l, r};
    }
}